/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <iostream>

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
    RC ret = pf.open(indexname, mode);
    if (ret != 0){
		//cout<<"open failed" << endl;
        return ret;
	}
	char buffer[1024];
    IndexFileInfo *fileInfo;

    ret = pf.read(0, (void*)buffer);
	if(ret == RC_INVALID_PID){
		rootPid = 1;
        treeHeight = 0;
		IndexFileInfo fileInfo;
		fileInfo.rootPid = rootPid;
		fileInfo.treeHeight = treeHeight;
		ret = pf.write(0, (const void *)&fileInfo);
		return ret;
	}
    else if (ret != 0){
        return ret;
	}
	fileInfo = (IndexFileInfo *) buffer;
    rootPid = fileInfo->rootPid;
    treeHeight = fileInfo->treeHeight;
    return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
    IndexFileInfo fileInfo;
    RC ret;
    fileInfo.rootPid = rootPid;
    fileInfo.treeHeight = treeHeight;
    ret = pf.write(0, (const void *)&fileInfo);
    if (ret != 0)
        return ret;
    ret = pf.close();
    return ret;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
    RC ret;
    PageId pid1;
    //If this is the first insert on the tree
    if (treeHeight == 0)
    {
		//cout<<"creating a root"<<endl;
        BTLeafNode lNode;
        lNode.init();
        ret = lNode.insert(key, rid);
        if (ret != 0)
            return ret;
		ret = lNode.setNextNodePtr(0);
        ret = lNode.write(1, pf);
		if (ret != 0)
			return ret;
        rootPid = 1;
        treeHeight = 1;
    } else {
        bool childSplit;
        int childSplitKey;
        PageId childPid;
        ret = BTreeIndex::insert(key, rid, rootPid, 0, childSplit, childSplitKey, childPid);
        if (ret != 0)
            return ret;
        //If the root node split
        if (childSplit)
        {
			//cout<<"child split!"<<endl;
            //Create new root non-leaf node
            BTNonLeafNode rootNode;
            rootNode.initializeRoot(rootPid, childSplitKey, childPid);
            pid1 = pf.endPid();
            ret = rootNode.write(pid1, pf);
			if (ret != 0)
				return ret;
            rootPid = pid1;
            treeHeight++;
        }
    }
    return ret;
}

RC BTreeIndex::insert(int key, const RecordId& rid, PageId pid, int currentLevel, bool& split, int& splitKey, PageId& childPid)
{
    RC ret;
    split = false;
    PageId pid1, pid2;
    bool childSplit = false;
    int childSplitKey;
    //Leaf node (base case)
    if(treeHeight == currentLevel+1)
    {
        BTLeafNode lNode;
        ret = lNode.read(pid, pf);
        if (ret != 0)
            return ret;
        ret = lNode.insert(key, rid);

        //If the leaf node is full, and we must split
        if (ret == RC_NODE_FULL) {
            BTLeafNode sibling;
            int siblingKey;
			//cout<< "Splitting pid " << pid << endl; 
            ret = lNode.insertAndSplit(key, rid, sibling, siblingKey);
            if(ret != 0)
                return ret;
            pid1 = pf.endPid();
            //Get next node pointer of existing node
            //pid2 = lNode.getNextNodePtr();
            //Set next node pointer of existing node to the new sibling node
            lNode.setNextNodePtr(pid1);
            //Set the new sibling node's next node pointer to the existing node's
            //next node pointer
            //sibling.setNextNodePtr(pid2); (This should already be set.
			//cout<< "set next node pointers to " << pid2 << " and " << pid1<< endl;
            split = true;
            splitKey = siblingKey;
            childPid = pid1;
			ret = sibling.write(pid1, pf);
            if(ret != 0)
                return ret;
			BTLeafNode test;
			test.read(pid1, pf);
			//cout<< "written node pointer was: " << test.getNextNodePtr()<<endl;
        }
		lNode.write(pid, pf);
    }
    //Non-leaf node
    else {
        BTNonLeafNode nlNode;
        ret = nlNode.read(pid, pf);
        if (ret != 0)
            return ret;
        nlNode.locateChildPtr(key, pid1);
        BTreeIndex::insert(key, rid, pid1, currentLevel+1, childSplit, childSplitKey, pid2);
        //If the child split, this node must insert a new value
        if (childSplit)
        {
			//TEST
			//BTLeafNode test;
			//test.read(pid1, pf);
			//cout<< "child (" << pid1 << ") node pointer was: " << test.getNextNodePtr()<<endl;
			//test.read(pid2, pf);
			//cout<< "sibling (" << pid2 << ") node pointer was: " << test.getNextNodePtr()<<endl;
			//END TEST
		
            RecordId rid;
            rid.pid = pid2;
            ret = nlNode.insert(childSplitKey, rid);
            if (ret == RC_NODE_FULL) {
                BTNonLeafNode sibling;
                int siblingKey;
                ret = nlNode.insertAndSplit(childSplitKey, pid2, sibling, siblingKey);
                if (ret != 0)
                    return ret;
                pid1 = pf.endPid();
                ret = sibling.write(pid1, pf);
                if (ret != 0)
                    return ret;
                split = true;
                splitKey = siblingKey;
                childPid = pid1;
            }
			nlNode.write(pid, pf);
        }
    }
    return ret;
}
/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
    BTLeafNode lNode;
    BTNonLeafNode nlNode;
    RC ret;
    PageId pid = rootPid;
    int eid;
    for (int currentLevel = 0; treeHeight > currentLevel; currentLevel++)
    {
        // This case is for the leaf node
        if (treeHeight == currentLevel+1)
        {
            ret = lNode.read(pid, pf);
            if (ret != 0)
                return ret;
            ret = lNode.locate(searchKey, cursor.eid);
            if (ret != 0)
                return ret;
            cursor.pid = pid;
        }
        //Non Leaf Node Case
        else {
            ret = nlNode.read(pid, pf);
            if (ret != 0)
                return ret;
            ret = nlNode.locateChildPtr(searchKey, pid);
            if (ret != 0)
                return ret;
        }
    }
    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	RC rc;
	BTLeafNode node;
	if(cursor.pid == 0)
		return RC_INVALID_CURSOR;
	rc = node.read(cursor.pid, pf);
	if(rc !=0)
		return rc;
	rc = node.readEntry(cursor.eid, key, rid);
	if(rc !=0)
		return rc;
	if(cursor.eid +1 == node.getKeyCount() ){
		cursor.pid = node.getNextNodePtr();
		cursor.eid = 0;
	}else{
		cursor.eid ++;
	}
    return rc;
}

void BTreeIndex::printTree(){
	printTree(rootPid, 0);
}

void BTreeIndex::printTree(PageId currentpid, int depth){
	if(treeHeight-depth <= 0)
		return;
	cout << "Depth: " << depth << endl;
	BTNode node;
	node.read(currentpid, pf);
	cout << "pid: " << currentpid << endl;
	node.print();
	if(treeHeight-depth ==1){
		//leaf node
		BTLeafNode lNode;
		lNode.read(currentpid, pf);
		cout<<"next node pointer: "<< lNode.getNextNodePtr() << endl;
		return;
	}
	for(int i=0; i<node.getKeyCount()+1; i++){
		int key;
		RecordId rid;
		node.readEntry(i, key, rid);
		printTree(rid.pid, depth+1);
	}
}
